#include<iostream>
#include<vector>
#include<map>
using namespace std;

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        int word_l = words[0].size();
        int str_l = s.size(); int words_digit = words.size();
        map<string, int> ma;
        int left = 0;
        // cout << words_digit;
        for (int i = 0; i < str_l; i += word_l) {
            for (int j = 0; j < words_digit; j++) {
                if (s.compare(i, word_l, words[j]) == 0) {
                    // cout << 1 <<endl;
                    ma[words[j]]++; // s.substr(i,word_l)
                }
            }
            while ((i - left) / word_l + 1> words_digit) {
                if (ma.find(s.substr(left, word_l)) != ma.end()) {
                    ma[s.substr(left, word_l)]--;
                    if (ma[s.substr(left, word_l)] <= 0)
                        ma.erase(s.substr(left, word_l));
                    // cout << ma.size();
                }
                left += word_l;
            }
            if (ma.size() == words_digit) ans.push_back(left);
        }
        return ans;
    }
};

int main()
{
    string s = "barfoothefoobarman";
    vector<string> vt{ "foo","bar" };
    vector<int> ans = Solution().findSubstring(s, vt);
    for (auto& e : ans) {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        map<string, int> word_digit_map;
        for (int i = 0; i < words.size(); i++) {
            word_digit_map[words[i]]++;
        }
        vector<int> ans;
        int word_l = words[0].size();
        int str_l = s.size(); int words_digit = words.size();
        map<string, int> ma;
        int left = 0;
        // cout << words_digit;
        for (int i = 0; i < str_l; i += word_l) {
            for (int j = 0; j < words_digit; j++) {
                if (s.compare(i, word_l, words[j]) == 0) {
                    // cout << 1 <<endl;
                    ma[words[j]]++; // s.substr(i,word_l)
                }
            }
            while ((i - left) / word_l + 1 > words_digit) {
                if (ma.find(s.substr(left, word_l)) != ma.end()) {
                    ma[s.substr(left, word_l)]--;
                    if (ma[s.substr(left, word_l)] <= 0)
                        ma.erase(s.substr(left, word_l));
                    // cout << ma.size();
                }
                left += word_l;
            }
            // if(ma.size() == words_digit) ans.push_back(left);
            int flag = 1;
            for (int j = 0; j < words_digit; j++) {
                if (ma[words[j]] != word_digit_map[words[j]]) {
                    flag = 0;
                }
            }
            if (flag) ans.push_back(left);
        }
        return ans;
    }
};

// for(int j = 0;j < words_digit;j++){
           //     if(s.compare(i, word_l, words[j]) == 0){

           //     }
           // }